#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    int possibleStringCount(string word){
        int n=word.size(); unordered_set<string> st; st.insert(word);
        for(int i=0,j=0;i<n;i++){
            if(i==n-1||word[i]!=word[i+1]){
                string p=word.substr(0,j);
                for(int t=1;t<=i-j+1;t++){
                    p.push_back(word[i]);
                    st.insert(p+word.substr(i+1,word.size()-i-1));
                }
                j=i+1;
            }
        } return st.size();
    }
};

class Solution2 {
public:
    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            g[parent[i]].push_back(i);
        }

        int ancestor[26];
//        ranges::fill(ancestor, -1);
        memset(ancestor,-1,26);
        auto rebuild = [&](auto&& rebuild, int x) -> void {
            int sx = s[x] - 'a';
            int old = ancestor[sx];
            ancestor[sx] = x;
            for (int i = g[x].size() - 1; i >= 0; i--) {
                int y = g[x][i];
                int anc = ancestor[s[y] - 'a'];
                if (anc != -1) {
                    g[anc].push_back(y);
                    g[x][i] = -1; // -1 表示删除 y
                }
                rebuild(rebuild, y);
            }
            ancestor[sx] = old; // 恢复现场
        };
        rebuild(rebuild, 0);

        vector<int> size(n, 1); // 注意这里已经把 1 算进去了
        auto dfs = [&](auto&& dfs, int x) -> void {
            for (int y : g[x]) {
                if (y != -1) { // y 没被删除
                    dfs(dfs, y);
                    size[x] += size[y];
                }
            }
        };
        dfs(dfs, 0);
        return size;
    }
};

#define ll long long
class Solution3{
public:
    int maxSocre(int n,int K, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore){
        const ll INF=1e18; ll f[K+1][n];
        for(int i=0;i<=K;i++) for(int j=0;j<n;j++) f[i][j]=-INF;
        for(int j=0;j<n;j++) f[0][j]=0;
        for(int i=1;i<=K;i++)
            for(int j=0;j<n;j++){
                f[i][j]=f[i-1][j]+stayScore[i-1][j];
                for(int jj=0;jj<n;jj++)
                    if(j!=jj)
                        f[i][j]=max(f[i][j],f[i-1][jj]+travelScore[jj][j]);
            }
        ll ans=0;
        for(int j=0;j<n;j++) ans=max(ans, f[K][j]);
        return ans;
    }
};

class Solution4{
public:
    int possibleStringCount(string word, int k) {
        int n = word.size();
        if(n<k) return 0;
        const int MOD=1e9+7;
        vector<int> cnts; ll ans=1; int cnt=0;
        for(int i=0;i<n;i++){
            cnt++;
            if(i==n-1||word[i]!=word[i+1]){
                if(cnt>1) {
                    if (k > 0)
                        cnts.push_back(cnt - 1);
                    ans=ans*cnt%MOD;
                }
                k--;
                cnt=0;
            }
        }
        if(k<=0) return ans;
        int m=cnts.size();
        vector<vector<int>> f(m+1, vector<int>(k));
        f[0][0]=1;
        vector<int> s(k+1);
        for(int i=0;i<m;i++){
            for(int j=0;j<k;j++){
                s[j+1]=(s[j]+f[i][j])%MOD;
            }
            for(int j=0;j<k;j++){
                f[i+1][j]=(s[j+1]-s[max(j-cnts[i],0)])%MOD;
            }
        }
        ans-=reduce(f[m].begin(), f[m].end(), 0LL);
        return (ans%MOD+MOD)%MOD;
    }
};

int main(){
    Solution s; cout<<s.possibleStringCount("abbcccc")<<endl;

    vector<int> parent={-1,0,0,1,1,1};
    Solution2 s2; vector<int> ans2=s2.findSubtreeSizes(parent, "abaabc"); for(auto x: ans2) cout<<x<<" "; cout<<endl;

    vector<vector<int>> stayScore={{2,3}};
    vector<vector<int>> travelScore{{0,2},{1,0}};
    Solution3 s3; cout<<s3.maxSocre(2,1,stayScore, travelScore)<<endl;

    Solution4 s4; cout<<s4.possibleStringCount("aabbccdd",7)<<endl;
    return 0;
}